#define  SWAP( x, y )  { int t=x; x=y; y=t; }  
// 快速排序算法的非递归算法  
void quicksort_nonrecursive( int* A, int n )  
{  
    struct sbe  
    {  
        int beg;  
        int end;  
    };  
      
    sbe* arr = new sbe[n];  
  
    int  m;  
    int p;  
    int beg, end, i, j;  
  
    m = 0;  
    arr[0].beg = 0;  
    arr[0].end = n-1;  
  
    for ( ; ; )  
    {  
        if ( m < 0 )  
            break;  
        beg = arr[m].beg;  
        end = arr[m--].end;  
  
        if ( beg >= end )  
            continue;  
  
        // partition   
        p = A[beg];  
        i = beg;  
        j = end+1;  
        for ( ; ; )  
        {  
            while( ++i <= end && A[i] < p );  // ! while( A[++i] < p ); error  
            while( A[--j] > p );  
            if ( i > j )  
                break;  
            SWAP( A[i], A[j] );  
        }  
        SWAP( A[j], A[beg] );  
  
        arr[++m].beg = beg;  
        arr[m].end   = j-1;  
        arr[++m].beg = j+1;  
        arr[m].end   = end;  
    }  
  
    delete [] arr;  
}  
  
// 快速排序驱动程序  
void QuickSort( int* A      // 待排序数组  
              , int n       // 数组长度  
              , int method  // 采用方法，0 - 递归， 1 - 非递归  
              )  
{  
        quicksort_nonrecursive( A, n );  
}  
